/*判断身份证号是否合法*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int fun(char *a)//判断百岁老人
{
	if(strcmp(&a[12],"996")==0||
	strcmp(&a[12],"997")==0||
	strcmp(&a[12],"998")==0||
	strcmp(&a[12],"999")==0)
	return 1;
	else return 0;
}

int main()
{
	int n,check,length;
	char c[100],d[100],t2[]="10X98765432";
	scanf("%d",&n);
	getchar();
	for ( int i=0 ; i<n ; i++)
	{
		for ( int l = 0; l < 100; l++)
      	{
		  c[l] = '\0' ; 
		  d[l] = '\0' ;
		}
		gets(c);
		length = strlen(c);
		if( length == 18 )	//判断18位身份证号是否合法
		{
			check = (c[0] - '0') * 7 + (c[1] - '0') * 9 + (c[2] - '0') * 10 + (c[3] - '0') * 5 \
					+ (c[4] - '0') *8 + (c[5] - '0') * 4 + (c[6] - '0') * 2 + (c[7] - '0') * 1 \
					+ (c[8] - '0')*6 + (c[9] - '0') * 3 + (c[10] - '0') * 7 + (c[11] - '0') * 9 \
					+ (c[12] - '0') * 10 + (c[13] - '0')*5 + (c[14] - '0') * 8 + (c[15] - '0') * 4 \
					+ (c[16] - '0') * 2;
			check = t2[check % 11];		//计算校验码
										//判断校验码
				if ( check == c[17] )
				{
					printf("Valid\n");
					continue;
				}
				if ( check != c[17] );
				{
					printf("Invalid\n");
					continue;
				}
		}
		if ( length == 15 )	//将15位身份证号升级为18位
		{
			for ( int j=0 ; j<=5 ; j++ )
			{
				d[j] = c[j];
			}
			d[6]='1';
			if( fun(c))
			{
				d[7]='8';
			}
			else
			{
				d[7]='9';
			}
			for ( int k=8 ; k<=16 ; k++ )
			{
				d[k]= c[k-2];
			}
			check = (d[0] - '0') * 7 + (d[1] - '0') * 9 + (d[2] - '0') * 10 + (d[3] - '0') * 5 \
					+ (d[4] - '0') *8 + (d[5] - '0') * 4 + (d[6] - '0') * 2 + (d[7] - '0') * 1 \
					+ (d[8] - '0')*6 + (d[9] - '0') * 3 + (d[10] - '0') * 7 + (d[11] - '0') * 9 \
					+ (d[12] - '0') * 10 + (d[13] - '0')*5 + (d[14] - '0') * 8 + (d[15] - '0') * 4 \
					+ (d[16] - '0') * 2;
			check = check % 11;
			d[17]=t2[check];
			printf("%s\n",d);
			continue;
		}
		else
		{
			printf("Invalid\n");
			continue;
		}
	}
	return 0;
}